package main

import (
	"fmt"
)

type Tree struct {
	val int
	left *Tree
	right *Tree
}

// 构造函数
func NewNode(data int) *Tree {
	return &Tree{val:data}
}

// 递归前序遍历
func Preorder(t *Tree) {
	if t == nil {
		return
	}
	fmt.Printf("%5d", t.val)
	Preorder(t.left)
	Preorder(t.right)
}
// 递归中序遍历
func Inorder(t *Tree) {
	if t == nil {
		return
	}
	Inorder(t.left)
	fmt.Printf("%5d", t.val)
	Inorder(t.right)
}
// 递归后序遍历
func Postorder(t *Tree) {
	if t == nil {
		return
	}
	Postorder(t.left)
	Postorder(t.right)
	fmt.Printf("%5d", t.val)
}

// 非递归前序遍历
func (t *Tree)NoPreorder() []int {
	res := make([]int, 0)
	if t == nil {
		return res
	}
	stack := []*Tree{}
	for t != nil || len(stack) != 0 {
		if t != nil {
			res = append(res, t.val)  // 保存值
			stack = append(stack, t)  // 入栈
			t = t.left
		}else {
			t = stack[len(stack) - 1]
			stack = stack[:len(stack) - 1] // 出栈
			t = t.right
		}
	}

	return res
}

// 非递归中序遍历
func (t *Tree)NoInorder() []int {
	res := make([]int, 0)
	if t == nil {
		return res
	}
	stack := []*Tree{}
	for t != nil || len(stack) != 0 {
		if t != nil {
			stack = append(stack, t)  // 入栈
			t = t.left
		}else {
			t = stack[len(stack) - 1]
			res = append(res, t.val)  // 保存值
			stack = stack[:len(stack) - 1] // 出栈
			t = t.right
		}
	}

	return res
}

// 非递归后序遍历
func (t *Tree)NoPostorder() []int {
	res := make([]int, 0)
	if t == nil {
		return res
	}
	stack := []*Tree{}
	pre := &Tree{}
	stack = append(stack, t)  // 最后访问根节点
	for len(stack) != 0 {
		cur := stack[len(stack) - 1]   // 取出栈顶元素
		if (cur.left == nil && cur.right == nil) || (pre != nil && (pre == cur.left || pre == cur.right)) {
			res = append(res, cur.val)
			pre = cur
			stack = stack[:len(stack) - 1]
		}else {   // 先加入右节点，再加入左节点
			if cur.right != nil {
				stack = append(stack, cur.right)
			}
			if cur.left != nil {
				stack = append(stack, cur.left)
			}

		}
	}
	return res
}

// 层次遍历
func CengCiOrder(t *Tree) {
	if t == nil {
		return
	}
	queue := []*Tree{t}
	length := len(queue)
	for length > 0 {
		l := len(queue)
		for i := 0; i < l; i ++ {
			fmt.Printf("%5d", queue[i].val)
			if queue[i].left != nil {
				queue = append(queue, queue[i].left)
			}
			if queue[i].right != nil {
				queue = append(queue, queue[i].right)
			}
		}
		queue = queue[l:]
	}
}

func main() {
	root := NewNode(1)
	root.left = NewNode(2)
	root.right = NewNode(3)
	root.left.left = NewNode(4)
	root.right.left = NewNode(5)
	root.right.right = NewNode(6)

	Preorder(root)
	fmt.Println()
	fmt.Println(root.NoPreorder())

	fmt.Println("------------------")
	Inorder(root)
	fmt.Println()
	fmt.Println(root.NoInorder())

	fmt.Println("------------------")
	Postorder(root)
	fmt.Println()
	fmt.Println(root.NoPostorder())

	fmt.Println("----------------")
	CengCiOrder(root)
}
